package com.future.offer;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * Description: ��ָ Offer II 081. �����ظ�ѡ��Ԫ�ص����
 * ����һ�����ظ�Ԫ�ص�����������?candidates?��һ��������?target?��
 * �ҳ�?candidates?�����п���ʹ���ֺ�ΪĿ����?target?��Ψһ��ϡ�
 * <p>
 * candidates?�е����ֿ����������ظ���ѡȡ���������һ����ѡ����������ͬ������������ǲ�ͬ�ġ�?
 * <p>
 * ���ڸ��������룬��֤��Ϊ?target ��Ψһ��������� 150 ����
 * <p>
 * ʾ��?1��
 * <p>
 * ����: candidates = [2,3,6,7], target = 7
 * ���: [[7],[2,2,3]]
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode.cn/problems/Ygoe9J
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/5/12 18:04
 */
public class Solution_081 {

    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        System.out.println(combinationSum(candidates, target));
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (candidates == null || candidates.length == 0 || target < 0) {
            return ans;
        }
        process(candidates, 0, target, ans, new ArrayList<Integer>());
        return ans;
    }

    private static void process(int[] candidates, int index, int rest, List<List<Integer>> ans, List<Integer> tmp) {
        if (index == candidates.length) {
            if (rest == 0) {
                List<Integer> a = new ArrayList<Integer>() {{
                    addAll(tmp);
                }};
                a.sort(Comparator.comparing(o -> o));
                ans.add(a);
            }
            return;
        }
        for (int zhang = 0; zhang * candidates[index] <= rest; zhang++) {
            for (int i = 0; i < zhang; i++) {
                tmp.add(candidates[index]);
            }
            process(candidates, index + 1, rest - candidates[index] * zhang, ans, tmp);
            for (int i = 0; i < zhang; i++) {
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}
